/* -------------------------------------------------------------------
                          NXBitmapGraphicRep                     
        1. Definition
	   This class is designed to simply and effeciently implement
	   simple bitmap graphics operations and provide a method to
	   get them on the screen quickly.

	   Advanced bitmap stuff (lines, circles, polygon fills, etc.)
	   are left as an exercise for the programmer.

	2. Usage
	bitmap characteristics:
	  - initialization
	    initWithSize: aSize depth:aDepth andColor:aColor
		initializes the bitmap and allocates image data for an
image with a size of aSize, a pixel depth of aDepth and clears the
background to aColor.
	    initWithSize: depth:
	        same as above, but initializes background to black.

	  - drawing:
		plotPoint:x :y;
		erasePoint:x :y;
	plots a point in the current foreColor
	erases a point to the current backColor

	the rest of the methods are fairly self explanatory (and are
mostly documented within themselves.

	3. Theory
  When the bitmap is initialized, it's superclass allocates enough
data to hold an entire image at the initialized depth.  The image data
is stored in an array of unsigned char's.  The array is arranged
thusly:
               samp1=red, samp2=green, samp3=blu. 

24 bit color:  8 bits/sample, 3 samples/pixel, 3 bytes/pixel
[      pixel1       ][      pixel2       ]...
[samp1][samp2][samp3][samp1][samp2][samp3]...

12 bit color:  4 bits/sample, 3 samples/pixel, 1.5(!) bytes/pixel

[      pixel1       ][      pixel2       ][      pixel1       ]...
[samp1][samp2][samp3][samp1][samp2][samp3][samp1][samp2][samp3]...
[   data[0]  ][   data[1]  ][   data[2]  ][   data[3]  ][   data[4]  ]...

2 bit gray scale: 2 bits/pixel, 4 pixels/byte
[pix1][pix2][pix3][pix4][pix5][pix6][pix7][pix8]...
[       data[0]        ][       data[1]        ]...
NOTE: pix1 is in bits 7&8
      pix2 is in bits 5&6
      pix3 is in bits 3&4
      pix4 is in bits 1&2 etc...

Because of this arrangement, both plotPoint and erasePoint use bit
manipulation to deal with 12 bit and 2 bit color models.

Because of this, Color management is a bit strange:
Internally, all colors are represented as NXColor structures:  this
gives full support for CMYK, RGB, and HSB color models (just make sure
and use NeXT's color conversion routines).  

The colors are ALSO stored in an optimal form for doing bit level
pixel manipulation:

24 bit: cur_red, cur_grn, cur_blu all contain a full 8 bit byte with
the RGB intensity level for the corresponding color (0 is off, 255 is
full-on)

12 bit: same as 24 bit, but the bottom four bits are masked off.
Effectively giving 16 levels of color for each channel (4096 colors).

2 bit: gray_level contains the top 2 bits of the color level that has
been converted to a gray level.

By doing this, it ensures maximum throughput while avoiding any of
postscripts dithering muck.  Also, since internally, colors are
represented in the full NXColor way, you DO NOT lose color informaton
even if you are plotting in 2 bit gray-- as soon as you switch to a
deeper color model, this object will take advantage of it.

This object is designed to be hacked.  There are some fairly obvious
optimizations that could be done when implementing line-drawing or
poly-fills.

Remember:  bcopy(src, dest, #bytes) is a hell of a lot faster than a
fore-loop that does the same thing (check out the eraseFrame method).
------------------------------------------------------------------- */
#import "NXBitmapGraphicRep.h"

#import <appkit/color.h>
#import <appkit/graphics.h>
#import <string.h>
#import <stdio.h>
#import <math.h>
#import <c.h>
#import "miscutil.h"

#import "CmdVertex.h"
#import "CmdBgnpoly.h"
#import "CmdEndpoly.h"

extern void exit();
extern void *malloc();
extern void free();
@implementation NXBitmapGraphicRep : NXBitmapImageRep

#define RED24 0
#define GRN24 1
#define BLU24 2

// macro to convert x,y coordinates to offset from byte 0 of the data array
#define xyto24index(x,y) (((yh-y)*bytes_per_row)+(x*3))
#define xyto12index(x,y) (((yh-y)*bytes_per_row)+((3*x)/2))
#define xyto2index(x,y)  (((yh-y)*bytes_per_row)+(x/4))

- initBitmap
{
  int i;
  unsigned char *top_line;

  bytes_per_row=[self bytesPerRow];
  num_bytes=[self pixelsHigh]*bytes_per_row;
  data=[self data];

  yh=[self pixelsHigh]-1;

  // erase first line to back color
  for(i=0;i<[self pixelsWide];i++)
    [self erasePoint:i:0];
  
  switch(imageDepth){
  case NX_TwoBitGrayDepth:
    top_line=&data[xyto2index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto2index(0,i)]), bytes_per_row);
    break;
  case NX_TwelveBitRGBDepth:
    top_line=&data[xyto12index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto12index(0,i)]), bytes_per_row);
    break;
  case NX_TwentyFourBitRGBDepth:
    top_line=&data[xyto24index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto24index(0,i)]), bytes_per_row);
    break;
  }
  return self;
}

//    NX_DefaultDepth = 0,
//    NX_TwoBitGrayDepth = 258,
//    NX_EightBitGrayDepth = 264,
//    NX_TwelveBitRGBDepth = 516,
//    NX_TwentyFourBitRGBDepth = 520
- initWithSize:(NXSize *) aSize depth:(int) aDepth andColor:(NXColor)c;
{
  imageDepth=aDepth;
  [self setBackColor:c];
  switch(aDepth) {
  case NX_TwoBitGrayDepth:
    // this will yield a bitmap w/4 pixels per byte at 2 bits per pixel.
    [super initData:NULL     
     pixelsWide:aSize->width 
     pixelsHigh:aSize->height
     bitsPerSample:2       
     samplesPerPixel:1     
     hasAlpha:NO             
     isPlanar:NO               
     colorSpace:NX_OneIsWhiteColorSpace
     bytesPerRow:0         
     bitsPerPixel:0];
    break;
  case NX_TwelveBitRGBDepth:
    // this will yield a bitmap w/4 bits per sample and 3 samples per pixel.
    [super initData:NULL     
     pixelsWide:aSize->width 
     pixelsHigh:aSize->height
     bitsPerSample:4
     samplesPerPixel:3
     hasAlpha:NO             
     isPlanar:NO               
     colorSpace:NX_RGBColorSpace
     bytesPerRow:0         
     bitsPerPixel:0];
    break;
  case NX_TwentyFourBitRGBDepth:
    [super initData:NULL            // force NXBitmapImageRep to allocate data
     pixelsWide:aSize->width        // set the width
     pixelsHigh:aSize->height       // set the height
     bitsPerSample:8                // set the # of bits per sample
     samplesPerPixel:3              // set the # of samples per pixel
     hasAlpha:NO                    // Do not want alpha channel
     isPlanar:NO                    // Data should be interleaved in one array
     colorSpace:NX_RGBColorSpace    // standard RGB color space
     bytesPerRow:0                  // allocate the data automatically
     bitsPerPixel:0];               // no filler bits anywhere
    break;
  default:
    fprintf(stderr, "GraphicsWrap: attempted to create bitmap for unsupported \
pixel depth. Bye!\n");
    exit(1);
  }    
  [self initBitmap];              // initialize instance variables &
                                  // clear data
  return self;
}

- initWithSize:(NXSize *) aSize andDepth:(int) aDepth
{
  [self initWithSize:aSize depth:aDepth
   andColor:NXConvertRGBToColor(0.0, 0.0, 0.0)];
  return self;
}

// erases the current frame to aColor
- eraseFrameToColor:(NXColor) aColor
{
  [self setBackColor:aColor];
  [self eraseFrame];
  return self;
}

// erases the current frame to backColor
- eraseFrame
{
  int i;
  unsigned char *top_line;
  
  // erase first line to back color
  for(i=0;i<[self pixelsWide];i++)
    [self erasePoint:i:0];
  
  switch(imageDepth){
  case NX_TwoBitGrayDepth:
    top_line=&data[xyto2index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto2index(0,i)]), bytes_per_row);
    break;
  case NX_TwelveBitRGBDepth:
    top_line=&data[xyto12index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto12index(0,i)]), bytes_per_row);
    break;
  case NX_TwentyFourBitRGBDepth:
    top_line=&data[xyto24index(0,0)];
    for(i=0;i<[self pixelsHigh];i++)
      bcopy(top_line, &(data[xyto24index(0,i)]), bytes_per_row);
    break;
  }
  return self;
}

- plotPoint:(long)x :(long)y
{
  long index;

  if(x<0 || x>=[self pixelsWide] || y<0 || y>=[self pixelsHigh]) {
    fprintf(stderr, "Coordinate out of bound: %d,%d\n", x, y);
    return self;
  }
  
  switch(imageDepth){
  case NX_TwentyFourBitRGBDepth: 
    index=xyto24index(x,y);
    data[index+RED24]=cur_red;
    data[index+GRN24]=cur_grn;
    data[index+BLU24]=cur_blu;
    break;
  case NX_TwelveBitRGBDepth:
    index=xyto12index(x,y);
    // these only work because of the bit munging done in setColor
    // RED
    data[index]=
      // if x is odd
      (x & 0x01) ?
	// set the bottom 4 bits of index to the top 4 bits of
	// the current red in a most peculiar fashion
	((cur_red >> 4) | (data[index] & 0xf0)) :
	  // else, x is even
	  // set the top 4 bits of index to the top 4 bits of red
	  (cur_red | (data[index] & 0x0f));

    // GREEN
    // if x is odd
    if (x & 0x01)
      data[index+1]=
	// set the top 4 bits of (index+1) to the top 4 bits of
	// the current green in an even more peculiar fashion
	(cur_grn | (data[index+1] & 0x0f));
    else 
      data[index]=
	// set the bottom 4 bits of (index) to the top 4 bits of
	// the current green
	((cur_grn >> 4) | (data[index] & 0xf0));

    // BLUE
    data[index+1]=
      (x & 0x01) ?
	// set the bottom 4 bits of (index+1) to the top 4 bits of
	// the current blue
	((cur_blu >> 4) | (data[index+1] & 0xf0)) :
	  // else, x is even and we need to set the top 4 bits of (index+1)
	  // to the top 4 bits of the current blue
	  (cur_blu | (data[index+1] & 0x0f));
    break;
  case NX_TwoBitGrayDepth:
    index=xyto2index(x,y);
    switch(x%4){
      // 63 is binary 00111111
    case 0:data[index]=(data[index] & 63) | gray_level;
      break;
      // 207 is binary 11001111
    case 1:data[index]=(data[index] & 207) | (gray_level>>2);
      break;
      // 243 is binary 11110011
    case 2:data[index]=(data[index] & 243) | (gray_level>>4);
      break;
      // 252 is binary 11111100
    case 3:data[index]=(data[index] & 252) | (gray_level>>6);
      break;
    }
  }
  return self;
}

- erasePoint:(long)x :(long)y
{
  long index;

  if(x<0 || x>=[self pixelsWide] || y<0 || y>=[self pixelsHigh]) {
    fprintf(stderr, "Coordinate out of bound: %d,%d\n", x, y);
    return self;
  }

  switch(imageDepth){
  case NX_TwentyFourBitRGBDepth: 
    index=xyto24index(x,y);
    data[index+RED24]=bck_red;
    data[index+GRN24]=bck_grn;
    data[index+BLU24]=bck_blu;
    break;
  case NX_TwelveBitRGBDepth:
    index=xyto12index(x,y);
    // these only work because of the bit munging done in setColor
    // RED
    data[index]=
      // if x is odd
      (x & 0x01) ?
	// set the bottom 4 bits of index to the top 4 bits of
	// the current red in a most peculiar fashion
	((bck_red >> 4) | (data[index] & 0xf0)) :
	  // else, x is even
	  // set the top 4 bits of index to the top 4 bits of red
	  (bck_red | (data[index] & 0x0f));

    // GREEN
    // if x is odd
    if (x & 0x01)
      data[index+1]=
	// set the top 4 bits of (index+1) to the top 4 bits of
	// the current green in an even more peculiar fashion
	(bck_grn | (data[index+1] & 0x0f));
    else 
      data[index]=
	// set the bottom 4 bits of (index) to the top 4 bits of
	// the current green
	((bck_grn >> 4) | (data[index] & 0xf0));

    // BLUE
    data[index+1]=
      (x & 0x01) ?
	// set the bottom 4 bits of (index+1) to the top 4 bits of
	// the current blue
	((bck_blu >> 4) | (data[index+1] & 0xf0)) :
	  // else, x is even and we need to set the top 4 bits of (index+1)
	  // to the top 4 bits of the current blue
	  (bck_blu | (data[index+1] & 0x0f));
    break;
  case NX_TwoBitGrayDepth:
    index=xyto2index(x,y);
    switch(x%4){
      // 63 is binary 00111111
    case 0:data[index]=(data[index] & 63) | bck_gray_level;
      break;
      // 207 is binary 11001111
    case 1:data[index]=(data[index] & 207) | (bck_gray_level>>2);
      break;
      // 243 is binary 11110011
    case 2:data[index]=(data[index] & 243) | (bck_gray_level>>4);
      break;
      // 252 is binary 11111100
    case 3:data[index]=(data[index] & 252) | (bck_gray_level>>6);
      break;
    }
  }
  return self;
}

- setColor:(NXColor)aColor
{
  float red,green,blue,gray;
  int r,g,b;
  NXConvertColorToRGB(aColor, &red, &green, &blue);
  r=floattobyte(red); g=floattobyte(green); b=floattobyte(blue);

  foreColor=aColor;
  switch(imageDepth){
  case NX_TwelveBitRGBDepth:
    // strip bottom four bits off all colors since they are not used
    // speeds up the point plotting stuff
    cur_red=r & 0xf0;
    cur_grn=g & 0xf0;
    cur_blu=b & 0xf0;
    break;
  case NX_TwentyFourBitRGBDepth:
    cur_red=r; cur_grn=g; cur_blu=b;
    break;
  case NX_TwoBitGrayDepth:
    NXConvertColorToGray(aColor, &gray);
    gray_level=floattobyte(gray) & 0xc0;
    break;
  }
    return self;
}

- setBackColor:(NXColor)aColor
{
  float red,green,blue,gray;
  int r,g,b;
  NXConvertColorToRGB(aColor, &red, &green, &blue);
  r=floattobyte(red); g=floattobyte(green); b=floattobyte(blue);

  backColor=aColor;
  switch(imageDepth){
  case NX_TwelveBitRGBDepth:
    // strip bottom four bits off all colors since they are not used
    // speeds up the point plotting stuff by eliminating this
    // operation from the plotPoint/erasePoint routines.
    bck_red=r & 0xf0;
    bck_grn=g & 0xf0;
    bck_blu=b & 0xf0;
    break;
  case NX_TwentyFourBitRGBDepth:
    bck_red=r; bck_grn=g; bck_blu=b;
    break;
  case NX_TwoBitGrayDepth:
    NXConvertColorToGray(aColor, &gray);
    bck_gray_level=floattobyte(gray) & 0xc0;
    break;
  }
  [self eraseFrame];
  return self;
}

- (NXColor)color
{
  return foreColor;
}

-(NXColor)backColor
{
  return backColor;
}

- (int)imageDepth
{
  return imageDepth;
}

// modelled after the routine on page 78 of _Computer Graphics:
//   Princliples and Practice
// this line method actually special cases for 8 quadrants for the
// line.  By doing this, the line ALWAYS starts at x0,y0 to x1,y1.  This
// is a GOOD THING when doing patterns and such that need to flow from
// the start point to the end point only.
// QUADRANTS:  1|2
//             -+-
//             3|4
// Each quadrant is divided into halves at the 45 degree mark.
int curX, curY;

- line:(int)x0 :(int)y0 :(int)x1 :(int)y1
{
  long dx, dy, incD, incDD, d, x, y;
  long xadd, yadd;
  dx=ABS(x1-x0); dy=ABS(y1-y0);

  if(x0>x1) {
    if(y0>y1) {
      // down and to the left
      xadd=-1; yadd=-1;
    } else {
      // up and to the left
      xadd=-1; yadd=1;
    }
  } else {
    if(y0>y1) {
      xadd=1; yadd=-1;
    } else {
      xadd=1; yadd=1;
    }
  }
  x=x0; y=y0;
  [self plotPoint:x :y];

  if(dx<dy){
    d=2*dx-dy;
    incD=2*dx;
    incDD=2*(dx-dy);
    while(y!=y1){
      if(d<=0) d+=incD; else {
	d+=incDD; x+=xadd;
      }
      y+=yadd;
      [self plotPoint:x :y];
    }
  } else {
    d=2*dy-dx;
    incD=2*dy;
    incDD=2*(dy-dx);
    while(x!=x1){
      if (d<=0) d+=incD; else {
	d+=incDD; y+=yadd;
      }
      x+=xadd;
      [self plotPoint:x :y];
    }
  }
  
  return self;
}

// TGIF commands
- cmdDraw:(int)x :(int)y
{
  [self line:curX :curY :x :y];
  [self cmdMove:x :y];
  return self;
}
- cmdMove:(int)x :(int)y
{
  curX=x; curY=y; return self;
}

- cmdCircle:(int)r
{
  // draw circle of radius r at current cursor location
  return self;
}

- cmdFps:(int)f
{
  // set frames per second
  return self;
}

- cmdHold:(int)seconds
{
  // set the hold value
  return self;
}

- cmdNewframe
{
  // hold for hold value and erase the image
  [self eraseFrame];
  return self;
}

typedef struct _ETelem {
  int xmin, ymax, xmax;    // only need these coordinates. ymin is curLine.
  // xmax is only used for right-edge collision detection.
  int num, den, inc; // state variables of integer line calculation
  int xinc;
  BOOL leftEdge;     // left or right edge-- approximation direction.
  struct _ETelem *next;
} ETelem;

void addtoedgetable(ETelem **etable, ETelem *edge, int curLine)
{
  ETelem *list;
  // if nothing on this scan line yet, add edge to this line.
  if(!etable[curLine]) etable[curLine]=edge;
  else {
    // something on this line.  Deal.
    if(edge->xmin < etable[curLine]->xmin) {
      // add as first element
      edge->next=etable[curLine];
      etable[curLine]=edge;
    } else {
      // traverse list at the current ymin
      list=etable[curLine];
      while(list->next && (list->next->xmin < edge->xmin))
	list=list->next;
      edge->next=list->next;
      list->next=edge;
    }
  }
}

- cmdDrawPoly:vertexList
{
  ETelem **etable, *edge;
  int s, e, numVerts, count, i, j;
  id  sV, eV;
  int sX=0, sY, eX, eY;
  ETelem *aet=(ETelem *)nil, *list, *aeTmp, *array[256];
  int curLine=0, topLine=0;
  BOOL drawing=NO;

  if (!([[vertexList removeObjectAt:0] isMemberOf:[CmdBgnpoly class]])){
    fprintf(stderr, "Polygon rejected:  No bgnpoly command found.\n");
    return nil;
  }
  if (!([[vertexList removeLastObject] isMemberOf:[CmdEndpoly class]])){
    fprintf(stderr, "Polygon rejected:  No endpoly command found.\n");
    return nil;
  }
  
  // allocate edgetable-- currently allocated to be the number of scanlines
  // in the entire image.  Ineffecient use of memory.
  etable=(ETelem **) malloc(sizeof(ETelem *) * [self pixelsHigh]);
  // set pointers to null
  bzero(etable, sizeof(ETelem *)*[self pixelsHigh]);

  // fill edge table
  for(numVerts=[vertexList count],s=0,e=1;s<numVerts;s++, e++){
    if(e==numVerts) e=0; // last vertice is end to beginning
    sV=[vertexList objectAt:s];
    eV=[vertexList objectAt:e];
    sX=[sV x]; sY=[sV y]; eX=[eV x]; eY=[eV y];

    edge=(ETelem *) malloc(sizeof(ETelem));
    edge->next=(ETelem *)nil;
    if(sY<eY){
      edge->xmin=sX; edge->ymax=eY;
      edge->xmax=eX;
      edge->num=eX-sX;
      edge->den=eY-sY;
      if (eY>topLine) topLine=eY;
      curLine=sY;
    } else {
      edge->xmin=eX; edge->ymax=sY;
      edge->xmax=sX;
      edge->num=sX-eX;
      edge->den=sY-eY;
      if (sY>topLine) topLine=sY;
      curLine=eY;
    }
    edge->inc=edge->den;
    if (edge->num > 0) edge->xinc=1; else edge->xinc=-1;
    addtoedgetable(etable, edge, curLine);
  }

  // build AET and process
  curLine=0;
  aet=(ETelem *)nil;
  // traverse to first scanline w/a vertex (no sense walking through everything
					 // before there is anything to
					 // process)
  while(!etable[curLine])curLine++;

  while(curLine<=topLine) {
    // add this scan-lines vertices to the AET (if any)
    if(etable[curLine]){
      if(!aet) aet=etable[curLine];
      else {
	// add to the end of the current AET
	aeTmp=aet;
	while(aeTmp && aeTmp->next) aeTmp=aeTmp->next;
	aeTmp->next=etable[curLine];
      }
    }
    // and sort the AET
    count=0;
    aeTmp=aet;
    array[count++]=aeTmp;
    // convert the linked list into an array to do the sort
    // because the programmer hates sorting algorithms w/a passion
    // and would rather use a pre-written one from K&R
    while(aeTmp && aeTmp->next) { aeTmp=aeTmp->next; array[count++]=aeTmp; }
    for(i=1; i<count; i++){
      aeTmp=array[i];
      for(j=i-1; (j>=0) && (array[j]->xmin > aeTmp->xmin); j--)
	array[j+1] = array[j];
      array[j+1]=aeTmp;
    }
    aet=array[0];
    for(i=1;i<count;i++){
      array[i-1]->next=array[i];
    }
    if(array[count-1]) array[count-1]->next=(ETelem *)nil;
    array[count]=(ETelem *)nil;

    // fill pixels.
    drawing=NO;
    for(aeTmp=aet; aeTmp; aeTmp=aeTmp->next){
      // avoid ymax==curLines points-- they do not count. (3.3)
      if(aeTmp->ymax>curLine)
	if(drawing){
	  // draw span
	  [self line:sX :curLine :aeTmp->xmin :curLine];
#ifdef DEBUG
	  fprintf(stderr,"Span: %d %d %d %d\n", sX, curLine,
		  aeTmp->xmin, curLine);
#endif
	  // toggle flag
	  drawing=NO;
	  aeTmp->leftEdge=NO; // this is a right edge
	} else {
	  // starting new span-- set start x
	  sX=aeTmp->xmin;
	  // toggle flag
	  drawing=YES;
	  aeTmp->leftEdge=YES; // this is a left edge
	}
    }    

    // remove y=ymax
    // strip from the head, if needed
    while(aet && aet->ymax==curLine) {
      aeTmp=aet;
      aet=aet->next;
      free(aeTmp);
    }
    list=aet;
    while(list && list->next){
      if(list->next->ymax==curLine)
	// cut out the edge
	list->next=list->next->next;
      list=list->next;
    }
    
    // update the yvalue
    curLine++;
    
    // update the xmin values on all edges that are left
    for(list=aet; list; list=list->next){
      // ignore vertical lines
      if(list->den){
	// increase the numerator
	list->inc+=ABS(list->num);
	while(list->inc > list->den){
	  list->xmin+=list->xinc;
	  list->inc-=list->den;
	}
      }
      if((list->xmax == list->xmin) && !list->inc) list->xmin-=1;
    }
  }
  return self;
}

@end
